﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include <vector>
using namespace std;
//
//int main(void)
//
//{
//
//	vector<int>array;
//
//	array.push_back(100);
//
//	array.push_back(300);
//
//	array.push_back(300);
//
//	array.push_back(300);
//
//	array.push_back(300);
//
//	array.push_back(500);
//
//	vector<int>::iterator itor;
//
//	for (itor = array.begin(); itor != array.end(); itor++)
//
//	{
//
//		if (*itor == 300)
//
//		{
//
//			itor = array.erase(itor);
//
//		}
//
//	}
//
//	for (itor = array.begin(); itor != array.end(); itor++)
//
//	{
//
//		cout << *itor << " ";
//
//	}
//
//	return 0;
//
//}


//给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

//class Solution 
//{
//public:
//    vector<vector<int>> generate(int numRows) 
//    {
//        vector<vector<int>>arr(numRows);
//        for (int i = 0; i < numRows; i++)
//        {
//            for (int j = 0; j < i+1; j++)
//            {
//                arr[i].push_back(1);
//            }
//        }
//        for (int i = 2; i < numRows; i++)
//        {
//            for (int j = 1; j < i; j++)
//            {
//                arr[i][j] = arr[i - 1][j] + arr[i - 1][j - 1];
//            }
//        }
//        return arr;
//    }
//};

//给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
// 元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
//
//考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
//
//更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
//返回 k 。
//nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]

//class Solution 
//{
//public:
//    int removeDuplicates(vector<int>& nums) 
//    {
//        if (nums.size() < 2)//小于等于1时直接返回
//        {
//            return nums.size();
//        }
//        vector<int>::iterator it = nums.begin();
//        int index = 1;//从下标1开始，也就是第二个数开始遍历
//        for (int i = 1; i < nums.size(); ++i)
//        {
//            if (nums[i] != nums[i - 1])
//            {
//                nums[index++] = nums[i];
//            }
//        }
//        return index;
//    }
//};


//给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
//
//你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
#include<algorithm>
//
//class Solution
//{
//public:
//    vector<int> singleNumber(vector<int>& nums)
//    {
//        if (nums.size() < 4)
//        {
//            return nums;
//        }
//        sort(nums.begin(), nums.end());
//
//        vector<int>num(2);
//        int index = 0;
//
//        for (int i = 0; i < nums.size() - 1; )
//        {
//            if (nums[i] == nums[i + 1])//如果这个数与后面一个数相同，直接让i+2
//            {
//                i += 2;
//            }
//            else//不同的话，第一个数肯定是只有一个的，所以记录后，在判断特殊情况，下一个数刚好在末尾，无法再次进入循环后，直接在记录下一个数
//            {
//                num[index++] = nums[i];
//                ++i;
//                if (i == nums.size() - 1)
//                {
//                    num[index++] = nums[i];
//                }
//            }
//        }
//        if (index == 1)//但也有特殊情况，第一个数在前面就找出来了，可第二个数在最后面，没有比较的机会就直接退出循环，此时只需要判断index下标是不是还在1的位置，是的话直接记录最后一个数
//        {
//            num[1] = nums[nums.size() - 1];
//        }
//        return num;
//    }
//};



//给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
//
//你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

#include<unordered_map>

//class Solution 
//{
//public:
//    int singleNumber(vector<int>& nums) 
//    {
//        unordered_map<int, int>num;
//        for (auto& it : nums)
//        {
//            num[it]++;
//        }
//        for (int i = 0; i < nums.size(); ++i)
//        {
//            if (num[nums[i]] == 1)
//            {
//                return nums[i];
//            }
//        }
//        return 0;
//    }
//};


class Solution 
{
public:
    int singleNumber(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        int flag = 0;
        for (int i = 0; i < nums.size()-1; ++i)
        {
            if (nums[i] == nums[i + 1])
            {
                i += 3;
            }
            else
            {
                return nums[i];
            }
        }
        return nums[nums.size() - 1];
    }
};

